package com.hanxiaozhang.no10leetcode.tree;


import java.util.ArrayList;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈给一棵二叉树和一个sum值，判断树中是否存在一条从根到叶的路径，使得这条路径的和为sum值。
 * 注意：叶节点的定义为没有子节点的节点〉
 * <p>
 * 实例:
 * 给定下面的二叉树和总和为 22,
 * .       5
 * .      / \
 * .     4   8
 * .    /   / \
 * .   11  13  4
 * .  /  \      \
 * . 7    2      1
 * 输出 true  5->4->11->2 which sum is 22.
 *
 * @author hanxinghua
 * @create 2024/4/12
 * @since 1.0.0
 */
public class No112PathSum {

    public static void main(String[] args) {

        TreeNode tree1 = new TreeNode(5);
        tree1.left = new TreeNode(4);
        tree1.right = new TreeNode(8);
        tree1.left.left = new TreeNode(11);
        tree1.right.left = new TreeNode(13);
        tree1.right.right = new TreeNode(4);
        tree1.left.left.left = new TreeNode(7);
        tree1.left.left.right = new TreeNode(2);
        tree1.right.right.right = new TreeNode(1);


        System.out.println(method1(tree1, 22));
        System.out.println(method2(tree1, 22));
    }


    /**
     * 方法1：自己的方法
     *
     * @param root
     * @param sum
     * @return
     */
    private static boolean method1(TreeNode root, Integer sum) {
        if (root == null) {
            return false;
        }
        List<List<Integer>> results = new ArrayList<>();
        List<Integer> result = new ArrayList<>();

        backtrack(results, result, root);

        for (List<Integer> integers : results) {
            if (sum == integers.stream().mapToInt(x -> x).sum()) {
                return true;
            }
        }

        return false;
    }

    private static void backtrack(List<List<Integer>> results, List<Integer> result, TreeNode root) {

        // 添加元素
        result.add(root.val);

        // 边界条件，判断当前是否为叶子节点 Tips:一开始没有想到
        if (root.left == null && root.right == null) {
            results.add(new ArrayList<>(result));
            // 恢复现场
            result.remove(result.size() - 1);
            return;
        }

        if (root.left != null) {
            backtrack(results, result, root.left);
        }
        if (root.right != null) {
            backtrack(results, result, root.right);
        }
        // 恢复现场
        result.remove(result.size() - 1);
    }


    /**
     * 方法2
     *
     * @param root
     * @param sum
     * @return
     */
    public static boolean method2(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }

        return recursive(root, sum, 0);
    }

    /**
     * 递归
     *
     * @param root
     * @param sum
     * @param currSum 当前和
     * @return
     */
    private static boolean recursive(TreeNode root, int sum, int currSum) {

        if (root == null) {
            return true;
        }

        // 判断是否为 叶子节点
        if (root != null && root.left == null && root.right == null) {
            return sum == (currSum + root.val);
        }

        // 累计当前值
        currSum += root.val;

        // 递归
        return recursive(root.left, sum, currSum) || recursive(root.right, sum, currSum);
    }
}
